package com.zwj.interview.链表;

/**
 * 给定两个表示非负整数的单向链表，请问如何实现这两个整数的相加并且把它们的和仍然用单向链表表示？
 * 1  2   3
 * <p>
 * 4  5   6
 */
public class 两个链表相加 {

    public ListNode addTwonumbers(ListNode head1, ListNode head2) {
        //先将两个链表反转，拿到每个整数的个位数
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        ListNode reversedHead = addReversed(head1, head2);
        return reverseList(reversedHead);
    }

    /**
     * 找到相加之后的头节点
     * 先将两个链表进行反转，这样就可以从个位数加起，相加之后产生的新节点
     * 重点在于考虑进位的问题
     * @param head1
     * @param head2
     * @return
     */
    private ListNode addReversed(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode sumNode = dummy;
        //进位
        int carry = 0;
        while (head1 != null || head2 != null) {
            int sum = (head1 == null ? 0 : head1.val) + (head2 == null ? 0 : head2.val) + carry;
            carry = sum >= 10 ? 1 : 0;
            sum = sum >= 10 ? sum - 10 : sum;
            ListNode newNode = new ListNode(sum);
            //产生的节点作为一个新的节点，放在sumNode的后面
            sumNode.next = newNode;
            //sumNode往后移动
            sumNode = sumNode.next;
            //往下不断移动两个链表的节点
            head1 = head1 == null ? null : head1.next;
            head2 = head2 == null ? null : head2.next;
        }
        if (carry > 0) {
            sumNode.next = new ListNode(carry);
        }
        return dummy.next;
    }




    public ListNode reverseList(ListNode head) {
        //1、变量prev指向当前节点的前一个节点
        ListNode prev = null;
        //2、变量cur指向当前遍历到的节点
        ListNode cur = head;
        while (cur != null) {
            //3、变量next指向当前节点的下一个节点
            ListNode next = cur.next;
            //真正执行反转
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}
